Levels and biological effects of selected EDC's in the portuguese coast

Os compostos orgânicos de estanho (OTs), de entre os quais se destaca o tributilestanho (TBT), encontram-se amplamente dispersos no meio aquático devido à sua intensa utilização como agente biocida em tintas antivegetativas. Estudos anteriores sobre a poluição por organoestanhos em Portugal demonstraram que estes compostos se encontram presentes não só na linha de costa mas também em zonas da plataforma, sendo as zonas portuárias (onde se incluem portos comerciais, portos de pesca, marinas e estaleiros navais) os principais focos de poluição. A presente tese tem como objectivo investigar o estado actual da poluição por organoestanhos na costa Portuguesa confirmando se os padrões espaciais acima descritos se mantêm, por meio da quantificação de diversos OTs, nomeadamente, butilestanhos, fenilestanhos e octilestanhos. Assim, os níveis destes compostos foram avaliados em populações de Mytilus galloprovincialis e Nassarius reticulatus ao longo da costa continental Portuguesa, com particular incidência na Ria de Aveiro onde se quantificaram os níveis de OTs em mexilhões, gastrópodes e sedimentos, recolhidos numa malha de amostragem mais densa. A distribuição espacial dos organoestanhos foi determinada utilizando o bivalve M. galloprovincialis como espécie bioindicadora. Os níveis totais de estanho (SnT) foram quantificados nos tecidos do mexilhão e relacionados com os níveis totais de OTs nos mesmos tecidos, incluindo monobutilestanho (MBT), dibutilestanho (DBT), tributilestanho (TBT), difenilestanho (DPhT), trifenilestanho (TPhT), monoctilestanho (MOcT) e dioctilestanho (DOct). A contribuição dos OTs para os valores de estanho total (SnT) foi superior nas estações de amostragem localizadas no interior de portos onde atingiram proporções próximas dos 50%. De entre estes, os butilestanhos (BuTs=MBT+DBT+TBT) contribuíram em média com 98.6% para o valor total de OTs, tendo sido detectados em todas as amostras analisadas. Os valores mais elevados foram registados no interior ou na proximidade de portos, corroborando a ideia anterior de que constituem importantes focos de poluição. A variação das concentrações de TBT no mexilhão situou-se entre os 0,9 e 720 ng Sn.g-1 de peso seco (ps). Estes valores são, em 69% das estações amostradas, superiores ao valor do proposto pela OSPAR (4,9 ng TBT-Sn.g-1 ps) para tecidos de mexilhão o que sugere a forte probabilidade de ocorrência de efeitos adversos sobre os ecossistemas. Os níveis de OTs foram também quantificados em tecidos de N. reticulatus recolhidos ao longo da costa em 2008 Os butilestanhos representaram a maioria dos compostos organoestânicos quantificados e os níveis mais elevados foram novamente detectados no interior ou nas imediações de portos. Os valores de TBT nos tecidos deste gastrópode variaram entre 3,5 e 380 ng Sn.g-1 ps, representando uma percentagem média de 50,4% do total de butilestanhos. Simultaneamente, os níveis de imposex foram também avaliados e relacionados com os valores deste composto nos tecidos. As distribuições espaciais de imposex e de TBT seguiram a mesma tendência, sendo que em todos os locais amostrados foram encontradas fêmeas afectadas. Os valores de VDSI (índice da sequência do vaso deferente) variaram entre 0,2 e 4,4. Em 91% dos locais os valores de VDSI foram superiores a 0,3 (definido pela OSPAR como o valor de VDSI em N. reticulatus acima do qual o objectivo de qualidade ecológica não é atingido), confirmando a suspeição da existência de efeitos adversos nos ecossistemas. Em todos os compartimentos analisados na Ria de Aveiro, os butilestanhos foram os principais contribuintes para estanho orgânico total. A utilização do imposex em N. reticulatus como biomarcador da poluição por TBT permitiu determinar um gradiente decrescente desde o interior da Ria (onde se situa a zona portuária) até zonas costeiras adjacentes. O mesmo gradiente foi observado relativamente às concentrações de TBT em tecidos de mexilhão. Para os sedimentos, as concentrações de TBT são bastante variáveis com valores entre 2,7 e 1780 ng Sn.g-1 ps encontrando-se significativamente correlacionadas com o conteúdo em matéria orgânica da amostra. Em todas as amostras analisadas os níveis de TBT são elevados e superiores ao valor inferior (provisório) de EAC (critério de avaliação ambiental) proposto pela OSPAR (0,004 ng TBT-Sn.g-1 ps). A análise da evolução temporal da poluição por TBT ao longo da costa foi concretizada por meio da comparação entre níveis de organoestanhos em N. reticulatus em amostras de 2008 e 2003 e também através da comparação dos níveis de imposex registados em campanhas realizadas naqueles dois anos. Os resultados obtidos indicam a ocorrência de reduções significativas nas concentrações de TBT, DBT e MBT, assim como uma diminuição significativa nos valores de VDSI entre 2003 e 2008. Os resultados obtidos sugerem que a redução verificada se deve à implementação do Regulamento 782/2003 da Comunidade Europeia, que tem por objectivo a erradicação das descargas e emissões de TBT para o ambiente a partir dos sistemas antivegetativos A diminuição da poluição por TBT ao longo dos últimos anos foi acompanhada por um aumento no número de fêmeas com um vaso deferente, mas sem pénis (imposex do tipo b): 3,5% em 2000, 11% em 2003 e 24% em 2008. Um aumento no número de locais onde se registou o fenómeno também é evidente: dois em 2000, sete em 2003 e treze em 2008. A proporção de fêmeas b no estádio 1 de VDS apresentou igual tendência com aumento de 38% em 2000 para 65% em 2008. O aumento no número de fêmeas com esta via parece estar associado à diminuição da poluição por TBT. Face à esperada diminuição da presença do composto no meio ambiente, devido à sua proibição, o aumento de fêmeas com imposex do tipo b é previsível. A ocorrência de compostos xenoestrogénicos no ambiente aquático foi também estudada e os níveis de estrona (E1), 17α-e 17β-estradiol (E2), 17α- etinilestradiol (EE2), bisfenol-A (BPA) e nonilfenol (NP) foram quantificados em efluentes de estações de tratamento de águas residuais (ETARs) localizadas na região de Aveiro, bem como no efluente final descarregado no Oceano Atlântico, através de um emissário submarino (S. Jacinto), sendo amostras recolhidas na entrada da Ria e ao largo usadas como referência. Os níveis de hormonas esteróides e compostos fenólicos registados nos locais de referência são baixos. De entre as hormonas esteróides os níveis mais elevados foram registados para a estrona, com valores máximos de 85.3 ng.L- 1 . Os níveis mais elevados de compostos fenólicos foram detectados em efluentes industriais (máximos de NP e BPA de 2410 ng.L-1 e 897 ng.L-1 , respectivamente). Os resultados obtidos sugerem que os níveis de compostos xenoestrogénicos em locais de referência são baixos e não parecerem acarretar risco ecológico, no entanto o mesmo não será verdadeiro para as imediações do emissário de S. Jacinto que liberta efluentes com concentrações muito elevadas de E1, NP e BPA. Foram realizadas experiências laboratoriais de forma a elucidar o papel do receptor retinóico X (RXR) no mecanismo de indução de imposex (presentemente o mecanismo que demonstra maior promessa na explicação do desencadear deste fenómeno). Fêmeas de Nucella lapillus e N. reticulatus foram injectadas com TBT em etanol ou com ácido 9-cis- retinóico em FBS (soro fetal bovino) tendo-se procedido à sua observação nos 30 dias subsequentes. Tanto o TBT como o 9CRA induziram o desenvolvimento de imposex em N. lapillus e N. reticulatus. Aumentos significativos nos valores de VDSI e FPL entre o controlo de etanol e o tratamento de TBT e o controlo de FBS e o tratamento de 9CRA foram registados. Os resultados obtidos fornecem novas provas do envolvimento da via de sinalização associada ao RXR no desenvolvimento de imposex em ambas as espécies.

Geometric optimization on visibility problems: metaheuristic and exact solutions

Os problemas de visibilidade têm diversas aplicações a situações reais. Entre os mais conhecidos, e exaustivamente estudados, estão os que envolvem os conceitos de vigilância e ocultação em estruturas geométricas (problemas de vigilância e ocultação). Neste trabalho são estudados problemas de visibilidade em estruturas geométricas conhecidas como polígonos, uma vez que estes podem representar, de forma apropriada, muitos dos objectos reais e são de fácil manipulação computacional. O objectivo dos problemas de vigilância é a determinação do número mínimo de posições para a colocação de dispositivos num dado polígono, de modo a que estes dispositivos consigam “ver” a totalidade do polígono. Por outro lado, o objectivo dos problemas de ocultação é a determinação do número máximo de posições num dado polígono, de modo a que quaisquer duas posições não se consigam “ver”. Infelizmente, a maior parte dos problemas de visibilidade em polígonos são NP-difíceis, o que dá origem a duas linhas de investigação: o desenvolvimento de algoritmos que estabelecem soluções aproximadas e a determinação de soluções exactas para classes especiais de polígonos. Atendendo a estas duas linhas de investigação, o trabalho é dividido em duas partes. Na primeira parte são propostos algoritmos aproximados, baseados essencialmente em metaheurísticas e metaheurísticas híbridas, para resolver alguns problemas de visibilidade, tanto em polígonos arbitrários como ortogonais. Os problemas estudados são os seguintes: “Maximum Hidden Vertex Set problem”, “Minimum Vertex Guard Set problem”, “Minimum Vertex Floodlight Set problem” e “Minimum Vertex k-Modem Set problem”. São também desenvolvidos métodos que permitem determinar a razão de aproximação dos algoritmos propostos. Para cada problema são implementados os algoritmos apresentados e é realizado um estudo estatístico para estabelecer qual o algoritmo que obtém as melhores soluções num tempo razoável. Este estudo permite concluir que as metaheurísticas híbridas são, em geral, as melhores estratégias para resolver os problemas de visibilidade estudados. Na segunda parte desta dissertação são abordados os problemas “Minimum Vertex Guard Set”, “Maximum Hidden Set” e “Maximum Hidden Vertex Set”, onde são identificadas e estudadas algumas classes de polígonos para as quais são determinadas soluções exactas e/ou limites combinatórios.

Dominating induced matchings

We study the problem of determining whether or not a graph G has an induced matching that dominates every edge of the graph, which is also known as efficient edge domination. This problem is known to be NP-complete in general as well as in some restricted domains, such as bipartite graphs or regular graphs. In this paper, we identify a graph parameter to which the complexity of the problem is sensible and produce results of both negative (intractable) and positive (solvable in polynomial time) type. © 2009 Springer Berlin Heidelberg.

Efficient edge domination in regular graphs

An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p ≥ 3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete. © 2008 Elsevier B.V. All rights reserved.

Compósitos de polímeros naturais e nanopartículas metálicas

Esta tese descreve diversas estratégias de preparação assim como a caracterização de nanocompósitos com base em distintos biopolímeros. Em particular foi estudada a incorporação de nanopartículas (NPs) metálicas, nomeadamente de Ag, Cu e Au. Estes nanomateriais apresentam um potencial prático enorme em diversas áreas, no entanto foi investigada especificamente a sua aplicação como materiais antimicrobianos. No primeiro capítulo apresenta-se uma revisão bibliográfica, onde são realçados os principais tópicos discutidos ao longo da tese. Inicialmente apresenta-se uma contextualização deste trabalho sendo seguidamente apresentadas algumas considerações sobre nanocompósitos e o seu impacto tecnológico atual. Em seguida, descrevem-se as vantagens do uso de NPs como cargas nos materiais compósitos especificamente no caso de bionanocompósitos. Foi focado o uso da celulose como matriz uma vez que foi o composto “base” usado neste trabalho. Fez-se a descrição exaustiva das metodologias existentes na literatura para a preparação dos nanocompósitos celulósicos com diferentes NPs metálicas assim como das respetivas aplicações. Dentro das aplicações, foi dado especial destaque às propriedades antimicrobianas dos materiais preparados seja a nível da sua atividade antibacteriana ou antifúngica. Esta introdução privilegia o trabalho relacionado diretamente com os sistemas descritos nos capítulos subsequentes. No segundo capítulo apresentam-se os resultados obtidos para nanocompósitos de prata em matriz celulósica. Através do uso de metodologias, tais como a síntese in situ e a pós-deposição, foram preparados diversos materiais usando dois substratos celulósicos distintos nomeadamente a celulose vegetal e bacteriana. Estes nanocompósitos foram caracterizados em termos da sua morfologia e composição química, verificando-se a importância destas características na sua atividade antibacteriana. Foi verificado que nanocompósitos com teores de Ag de 5 x 10-4 (% m/m) são suficientes para obter atividade antibacteriana. A libertação de Ag(I) foi estudada em alguns destes materiais de modo a tentar perceber o mecanismo subjacente a este tipo de nanocompósitos. No terceiro capítulo é apresentado o estudo de NPs coloidais de Ag e Au como cargas para a preparação de nanocompósitos à base de quitosano nãomodificado e modificado quimicamente (derivado solúvel em água e derivado anfifílico). Foram preparados filmes finos de espessura de 9-14 μm, caracterizando-se as suas propriedades óticas e antibacterianas. As propriedades óticas foram ajustadas, quer pela variação do teor de NPs de Ag (0,3-3,9% m/m) ou pela utilização de amostras de NPs com distribuição de tamanho de partícula distinta. Foi investigada a atividade antibacteriana tanto para bactérias Gram-negativas (Klebsiella pneumoniae e Escherichia coli) como para Gram-positivas (Staphylococcus aureus). Para nanocompósitos preparados com o quitosano não modificado verificou-se uma dependência em função do teor de Ag. No caso do uso de derivados modificados, os materiais preparados mostraram uma eficiência superior, mesmo sem NPs de Ag. No quarto capítulo é apresentada a síntese e caracterização de nanocompósitos de pululano e NPs de Ag. Neste estudo é avaliada a atividade antifúngica dos filmes compósitos preparados contra o Aspergillus niger usando protocolos padrão. Estes materiais foram preparados na forma de filmes (66-74 μm de espessura) por evaporação de solvente da mistura de pululano e coloides de Ag. Foi observado o aumento da inibição do fungo na presença dos nanocompósitos, tendo sido pela primeira vez mostrado o efeito disruptivo destes materiais sobre os esporos do A. niger através da análise das imagens de SEM. Este efeito ocorre na presença dos filmes devido à presença das cargas de NPs de Ag dispersas no pululano. O desenvolvimento de materiais de papel com NPs de Cu é um desafio devido à propensão destas espécies em oxidar sob condições ambiente. No quinto capítulo é descrita pela primeira vez o estudo comparativo do crescimento e estabilidade de NPs de Cu em celulose vegetal e bacteriana. Para além disso foi avaliado o uso de nanoestruturas com diferentes dimensionalidades como cargas, nomeadamente nanoesferas e nanofios. Foi observado que o uso de nanofios aumenta a resistência à oxidação destes nanocompósitos para tempos de exposição ao ar mais prolongados. As matrizes celulósicas apresentam comportamento distinto no crescimento e/ou adsorção das NPs de Cu. A celulose bacteriana foi o substrato mais eficiente para retardar a oxidação das NPs. A atividade antibacteriana destes nanocompósitos foi avaliada. Ao longo desta dissertação são apresentados métodos distintos para a obtenção de nanocompósitos com base em biopolímeros e NPs metálicas. Estes estudos permitiram não só a preparação de novos nanocompósitos mas também compreender e otimizar os mecanismos subjacentes à sua preparação. Ao mesmo tempo, este trabalho contribuiu para a transferência de tecnologia e conhecimento entre a área da Nanotecnologia e a área dos materiais derivados de fontes renováveis. As propriedades apresentadas por estes nanomateriais mostraram a sua possível aplicação como novos materiais antimicrobianos, no entanto é possível antecipar futuras aplicações em outras áreas tecnológicas.

Synthesis and functionalization of hydroxyapatite nanoparticles

Graças aos desenvolvimentos na área da síntese de nanomaterais e às potentes técnicas de caracterização à nanoescala conseguimos hoje visualizar uma nanopartícula (NP) como um dispositivo de elevado potencial terapêutico. A melhoria da sua efectividade terapêutica requer no entanto o aprofundamento e sistematização de conhecimentos, ainda muito incipientes, sobre toxicidade, selectividade, efeitos colaterais e sua dependência das próprias características físico-químicas da NP em análise. O presente trabalho, elegendo como alvo de estudo uma substância considerada biocompatível e não tóxica, a hidroxiapatite (Hap), pretende dar um contributo para esta área do conhecimento. Definiram-se como metas orientadoras deste trabalho (i) estudar a síntese de nanoparticulas de Hap (Hap NP), e a modificação das características físico-químicas e morfológicas das mesmas através da manipulação das condições de síntese; (ii) estudar a funcionalização das Hap NP com nanoestruturas de ouro e com ácido fólico, para lhes conferir capacidades acrescidas de imagiologia e terapêuticas, particularmente interessantes em aplicações como o tratamento do cancro (iii) estudar a resposta celular a materiais nanométricos, com propriedades físico-químicas diversificadas. No que se refere à síntese de Hap NP, comparam-se dois métodos de síntese química distintos, a precipitação química a temperatura fisiológica (WCS) e a síntese hidrotérmica (HS), em meios aditivados com ião citrato. A síntese WCS originou partículas de tamanho nanométrico, com uma morfologia de agulha, pouco cristalinas e elevada área superficial especifica. A síntese HS à temperatura de 180ºC permitiu obter partículas de dimensões também nanométricas mas com área específica inferior, com morfologia de bastonete prismático com secção recta hexagonal e elevada cristalinidade. Com o objectivo de aprofundar o papel de algumas variáveis experimentais na definição das características finais das partículas de hidroxiapatite, designadamente o papel do ião citrato (Cit), variou-se a razão molar [Cit/Ca] da solução reagente e o tempo de síntese. Demonstrou-se que o ião citrato e outras espécies químicas resultantes da sua decomposição nas condições térmicas (180ºC) de síntese tem um papel preponderante na velocidade de nucleação e de crescimento dessas mesmas partículas e por conseguinte nas características físico-químicas das mesmas. Elevadas razões [Cit/Ca] originam partículas de dimensão micrométrica cuja morfologia é discutida no contexto do crescimento com agregação. Com o objectivo de avaliar a citotoxicidade in vitro das nanopartículas sintetizadas procedeu-se à esterilização das mesmas. O método de esterilização escolhido foi a autoclavagem a 121º C. Avaliou-se o impacto do processo de esterilização nas características das partículas, verificando-se contrariamente às partículas WCS, que as partículas HS não sofrem alterações significativas de morfologia, o que se coaduna com as condições de síntese das mesmas, que são mais severas do que as de esterilização. As partículas WCS sofrem processos de dissolução e recristalização que se reflectem em alterações significativas de morfologia. Este estudo demonstrou que a etapa de esterilização de nanopartículas para aplicações biomédicas, por autoclavagem, pode alterar substancialmente as propriedades das mesmas, sendo pois criticamente importante caracterizar os materiais após esterilização. Os estudos citotoxicológicos para dois tipos de partículas esterilizadas (HSster e WCSster) revelaram que ambas apresentam baixa toxicidade e possuem potencial para a modelação do comportamento de células osteoblásticas. Tendo em vista a funcionalização da superfície das Hap NP para multifunções de diagnóstico e terapia exploraram-se condições experimentais que viabilizassem o acoplamento de nanopartículas de ouro à superfície das nanopartículas de Hidroxiapatite (Hap-AuNP). Tirando partido da presença de grupos carboxílicos adsorvidos na superfície das nanopartículas de Hap foi possível precipitar partículas nanométricas de ouro (1,5 a 2,5 nm) na superfície das mesmas adaptando o método descrito por Turkevich. No presente trabalho as nanopartículas de Hap funcionaram assim como um template redutor do ouro iónico de solução, propiciando localmente, na superfície das próprias nanopartículas de Hap, a sua redução a ouro metálico. A nucleação do ouro é assim contextualizada pelo papel redutor das espécies químicas adsorvidas, designadamente os grupos carboxílicos derivados de grupos citratos que presidiram à síntese das próprias nanopartículas de Hap. Estudou-se também a funcionalização das Hap NP com ácido fólico (FA), uma molécula biologicamente interessante por ser de fácil reconhecimento pelos receptores existentes em células cancerígenas. Os resultados confirmaram a ligação do ácido fólico à superfície das diferentes partículas produzidas HS e Hap-AuNPs. Graças às propriedades ópticas do ouro nanométrico (efeito plasmão) avaliadas por espectroscopia vis-UV e às potencialidades de hipertermia local por conversão fototérmica, as nanoestruturas Hap-AuNPs produzidas apresentam-se com elevado interesse enquanto nanodispositivos capazes de integrar funções de quimio e terapia térmica do cancro e imagiologia. O estudo da resposta celular aos diversos materiais sintetizados no presente trabalho foi alvo de análise na tentativa de se caracterizar a toxicidade dos mesmos bem como avaliar o seu desempenho em aplicações terapêuticas. Demonstrou-se que as Hap NP não afectam a proliferação das células para concentrações até 500 g/ml, observando-se um aumento na expressão genética da BMP-2 e da fosfatase alcalina. Verificou-se também que as Hap NP são susceptíveis de internalização por células osteoblásticas MG63, apresentando uma velocidade de dissolução intracelular relativamente reduzida. A resposta celular às Hap-AuNP confirmou a não citotoxicidade destas partículas e revelou que a presença do ouro na superfície das Hap NP aumenta a taxa proliferação celular, bem como a expressão de parâmetros osteogénicos. No seu conjunto os resultados sugerem que os vários tipos de partículas sintetizadas no presente estudo apresentam também comportamentos interessantes para aplicações em engenharia de tecido ósseo.

Majorantes para a ordem de subgrafos induzidos k-regulares

Muitos dos problemas de otimização em grafos reduzem-se à determinação de um subconjunto de vértices de cardinalidade máxima que induza um subgrafo k-regular. Uma vez que a determinação da ordem de um subgrafo induzido k-regular de maior ordem é, em geral, um problema NP-difícil, são deduzidos novos majorantes, a determinar em tempo polinomial, que em muitos casos constituam boas aproximações das respetivas soluções ótimas. Introduzem-se majorantes espetrais usando uma abordagem baseada em técnicas de programação convexa e estabelecem-se condições necessárias e suficientes para que sejam atingidos. Adicionalmente, introduzem-se majorantes baseados no espetro das matrizes de adjacência, laplaciana e laplaciana sem sinal. É ainda apresentado um algoritmo não polinomial para a determinação de umsubconjunto de vértices de umgrafo que induz umsubgrafo k-regular de ordem máxima para uma classe particular de grafos. Finalmente, faz-se um estudo computacional comparativo com vários majorantes e apresentam-se algumas conclusões.

Network virtualisation from an operator perspective

Network virtualisation is seen as a promising approach to overcome the so-called “Internet impasse” and bring innovation back into the Internet, by allowing easier migration towards novel networking approaches as well as the coexistence of complementary network architectures on a shared infrastructure in a commercial context. Recently, the interest from the operators and mainstream industry in network virtualisation has grown quite significantly, as the potential benefits of virtualisation became clearer, both from an economical and an operational point of view. In the beginning, the concept has been mainly a research topic and has been materialized in small-scale testbeds and research network environments. This PhD Thesis aims to provide the network operator with a set of mechanisms and algorithms capable of managing and controlling virtual networks. To this end, we propose a framework that aims to allocate, monitor and control virtual resources in a centralized and efficient manner. In order to analyse the performance of the framework, we performed the implementation and evaluation on a small-scale testbed. To enable the operator to make an efficient allocation, in real-time, and on-demand, of virtual networks onto the substrate network, it is proposed a heuristic algorithm to perform the virtual network mapping. For the network operator to obtain the highest profit of the physical network, it is also proposed a mathematical formulation that aims to maximize the number of allocated virtual networks onto the physical network. Since the power consumption of the physical network is very significant in the operating costs, it is important to make the allocation of virtual networks in fewer physical resources and onto physical resources already active. To address this challenge, we propose a mathematical formulation that aims to minimize the energy consumption of the physical network without affecting the efficiency of the allocation of virtual networks. To minimize fragmentation of the physical network while increasing the revenue of the operator, it is extended the initial formulation to contemplate the re-optimization of previously mapped virtual networks, so that the operator has a better use of its physical infrastructure. It is also necessary to address the migration of virtual networks, either for reasons of load balancing or for reasons of imminent failure of physical resources, without affecting the proper functioning of the virtual network. To this end, we propose a method based on cloning techniques to perform the migration of virtual networks across the physical infrastructure, transparently, and without affecting the virtual network. In order to assess the resilience of virtual networks to physical network failures, while obtaining the optimal solution for the migration of virtual networks in case of imminent failure of physical resources, the mathematical formulation is extended to minimize the number of nodes migrated and the relocation of virtual links. In comparison with our optimization proposals, we found out that existing heuristics for mapping virtual networks have a poor performance. We also found that it is possible to minimize the energy consumption without penalizing the efficient allocation. By applying the re-optimization on the virtual networks, it has been shown that it is possible to obtain more free resources as well as having the physical resources better balanced. Finally, it was shown that virtual networks are quite resilient to failures on the physical network.

O problema da árvore de suporte de custo mínimo com restrições de peso

Nesta tese abordam-se várias formulações e diferentes métodos para resolver o Problema da Árvore de Suporte de Custo Mínimo com Restrições de Peso (WMST – Weight-constrained Minimum Spanning Tree Problem). Este problema, com aplicações no desenho de redes de comunicações e telecomunicações, é um problema de Otimização Combinatória NP-difícil. O Problema WMST consiste em determinar, numa rede com custos e pesos associados às arestas, uma árvore de suporte de custo mínimo de tal forma que o seu peso total não exceda um dado limite especificado. Apresentam-se e comparam-se várias formulações para o problema. Uma delas é usada para desenvolver um procedimento com introdução de cortes baseado em separação e que se tornou bastante útil na obtenção de soluções para o problema. Tendo como propósito fortalecer as formulações apresentadas, introduzem-se novas classes de desigualdades válidas que foram adaptadas das conhecidas desigualdades de cobertura, desigualdades de cobertura estendida e desigualdades de cobertura levantada. As novas desigualdades incorporam a informação de dois conjuntos de soluções: o conjunto das árvores de suporte e o conjunto saco-mochila. Apresentam-se diversos algoritmos heurísticos de separação que nos permitem usar as desigualdades válidas propostas de forma eficiente. Com base na decomposição Lagrangeana, apresentam-se e comparam-se algoritmos simples, mas eficientes, que podem ser usados para calcular limites inferiores e superiores para o valor ótimo do WMST. Entre eles encontram-se dois novos algoritmos: um baseado na convexidade da função Lagrangeana e outro que faz uso da inclusão de desigualdades válidas. Com o objetivo de obter soluções aproximadas para o Problema WMST usam-se métodos heurísticos para encontrar uma solução inteira admissível. Os métodos heurísticos apresentados são baseados nas estratégias Feasibility Pump e Local Branching. Apresentam-se resultados computacionais usando todos os métodos apresentados. Os resultados mostram que os diferentes métodos apresentados são bastante eficientes para encontrar soluções para o Problema WMST.